import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class demo1 {
    List<List<String>>list;
    char[][]path;
    boolean[]col;
    boolean[]digz;
    boolean[]digf;
    public List<List<String>> solveNQueens(int n) {
        list=new ArrayList<>();
        path=new char[n][n];
        col=new boolean[n];
        digz=new boolean[2*n];
        digf=new boolean[2*n];
        for(int i=0;i<n;i++){
            Arrays.fill(path[i],'.');
        }
            dfs(n,0);
        return list;
    }
    public void dfs(int n,int pos){
        if(pos==n){
            List<String> lists=new ArrayList();
            for (int i = 0; i < n; i++) {
                lists.add(new String(path[i]));
            }
            list.add(lists);
            return;
        }
        for(int i=0;i<n;i++){
            if(!col[i]&&
                    !digz[pos-i+n]&&!digf[pos+i]){
                path[pos][i]='Q';
                col[i]=true;
                digz[pos-i+n]=true;
                digf[pos+i]=true;
                dfs(n,pos+1);
                col[i]=false;
                digz[pos-i+n]=false;
                digf[pos+i]=false;
                path[pos][i]='.';
            }
        }
    }
}
